package leetcode100

// TODO 动态规划 | 状态转移方程 [困难] 【-】 最长递增子序列
// TODO https://leetcode.cn/problems/longest-increasing-subsequence/solution/by-wwsw-7plk/

func lengthOfLIS(nums []int) (ans int) {
	dp := make([]int, len(nums))
	for i := range dp {
		dp[i] = 1
	} // 初始化，dp[i]表示递增子序列的长度
	for i := range nums {
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] { // nums[i] 可加入递增子序列
				dp[i] = max8(dp[i], dp[j]+1) // 有很多递增子序列，求这些最长递增子序列的最大长度
			}
		}
	}
	for _, d := range dp {
		ans = max(ans, d)
	}
	return
}

func max8(a, b int) int {
	if a > b {
		return a
	}
	return b
}
